/*******************************************
 * Copyright 2007 Aphrodite Framework for javaME .
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the GNU Public License v2.0
 * which accompanies this distribution, and is available at
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * Email : owner@aphroditeme.dev.java.net
 * Contributors:
 *     Kent Elton - initial API and implementation
 *******************************************/

/*
 * Created on Jun 25, 2007 at 11:12:23 AM.
 * 
 * Copyright (c) 2007 Robert Virkus / Enough Software
 *
 * This file is part of J2ME Polish.
 *
 * J2ME Polish is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * J2ME Polish is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with J2ME Polish; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Commercial licenses are also available, please
 * refer to the accompanying LICENSE.txt or visit
 * http://www.j2mepolish.org for details.
 */
package com.aphrodite.util.zip;

import java.io.IOException;
import java.io.InputStream;

/**
 * <p>
 * Utils for ZipInputStream and ZipOutputStream.
 * </p>
 * 
 */
final class ZipHelper {
	static final int[] DISTANCE_CODE = { 0, 1, 0, 2, 0, 3, 0, 4, 1, 5, 1, 7, 2, 9, 2, 13, 3, 17, 3, 25, 4, 33, 4, 49,
			5, 65, 5, 97, 6, 129, 6, 193, 7, 257, 7, 385, 8, 513, 8, 769, 9, 1025, 9, 1537, 10, 2049, 10, 3073, 11,
			4097, 11, 6145, 12, 8193, 12, 12289, 13, 16385, 13, 24577 };

	// constants:
	static final int[] LENGTH_CODE = { 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 1, 11, 1, 13, 1, 15, 1, 17, 2,
			19, 2, 23, 2, 27, 2, 31, 3, 35, 3, 43, 3, 51, 3, 59, 4, 67, 4, 83, 4, 99, 4, 115, 5, 131, 5, 163, 5, 195,
			5, 227, 0, 258 };
	/**
	 * This function converts the representation of a huffman tree from table to
	 * tree structure.
	 * 
	 * @param huffmanCode
	 *            input
	 * @param huffmanCodeLength
	 *            input
	 * @param huffmanData
	 *            input
	 * @param huffmanTree
	 *            resulting tree
	 */
	static final void convertTable2Tree(int[] huffmanCode, byte[] huffmanCodeLength, int[] huffmanData,
			short[] huffmanTree) {

		for (int i = 0; i < huffmanTree.length; i++) {
			huffmanTree[i] = 0;
		}

		short pointer;
		short nextNode = 1;
		// fill each code in
		short j;
		for (short i = 0; i < huffmanCode.length; i++) {
			if (huffmanCodeLength[i] != 0) {
				pointer = 0;
				for (j = 0; j < huffmanCodeLength[i]; j++) {

					if (huffmanTree[pointer * 2] == 0) {
						// undefined internal NODE
						huffmanTree[pointer * 2] = nextNode++;
						huffmanTree[pointer * 2 + 1] = nextNode++;
					}
					// go to known internal NODE
					pointer = huffmanTree[pointer * 2 + ((huffmanCode[i] >>> j) & 1)];

				}

				// set empty LEAF to data
				if (pointer < 0) {
					// #debug error
					System.out.println("error pointer=-1");
				}
				huffmanTree[pointer * 2] = -1;
				huffmanTree[pointer * 2 + 1] = (short) huffmanData[i];
			}
		}
	}

	/**
	 * This function computes / refreshes a crc32 checksum.
	 * 
	 * @param table
	 *            this is the precomputed crc32 table
	 * @param crc
	 *            set this value to zero if starting the computation or to the
	 *            last retrieved value when processing further data.
	 * @param buffer
	 *            the buffer to be walked
	 * @param off
	 *            the offset to start
	 * @param len
	 *            the amount of bytes to process
	 * @return the new/refreshed crc checksum
	 */
	public static final int crc32(int[] table, int crc, byte[] buffer, int off, int len) {
		if (table[2] == 0) {
			initCrc32Table(table);
		}

		crc = crc ^ 0xffffffff;

		for (int n = 0; n < len; n++) {
			crc = table[(crc ^ buffer[n + off]) & 0xff] ^ (crc >>> 8);
		}

		return 0xffffffff ^ crc;

	}

	/**
	 * This function parses and pops one huffmancode out of the given buffer and
	 * returs the associated value.
	 * 
	 * @param smallCodeBuffer
	 *            the buffer that is parsed
	 * @param huffmanTree
	 *            is the representation of the tree
	 * @return the data represented by the parsed huffman code
	 * @throws IOException
	 */
	static final int deHuffNext(long[] smallCodeBuffer, short[] huffmanTree) throws IOException {

		if (smallCodeBuffer[1] < 15) {
			// #debug error
			System.out.println("smallCodebuffer is too small");
		}

		short pointer = 0;

		while (huffmanTree[pointer * 2] != -1) {
			// go to next internal NODE
			pointer = huffmanTree[pointer * 2 + (int) (smallCodeBuffer[0] & 1)];
			smallCodeBuffer[0] >>>= 1;
			smallCodeBuffer[1]--;

			if (pointer == 0) {
				//System.out.println("small code buffer DAta "+smallCodeBuffer[0
				// ] + "\n");
				// error: in walking tree no leaf found
				throw new IOException("5");
			}

		}
		// return the data
		return huffmanTree[pointer * 2 + 1];

	}

	static final int encodeCode(int[] Code, int distance) {
		int i = 0;
		// while(i<Code.length/2 && distance>=Code[i*2+1]){i++;}
		while (i < (Code.length >> 1) && distance >= Code[(i << 1) + 1]) {
			i++;
		}
		// now: distance < Code[i*2+1]

		return i - 1;
	}

	/**
	 * Generate the fixed huffman trees as described in the rfc
	 * 
	 * @param huffmanCode
	 *            - pointer to where the code shall be inserted
	 * @param huffmanCodeLength
	 * @param distHuffCode
	 * @param distHuffCodeLength
	 */
	final static void genFixedTree(int[] huffmanCode, byte[] huffmanCodeLength, int[] distHuffCode,
			byte[] distHuffCodeLength) {

		int i;
		// huffmanCodes
		for (i = 0; i <= 143; i++) {
			huffmanCode[i] = 48 + i; // 48==00110000
			huffmanCodeLength[i] = 8;
		}
		for (i = 144; i <= 255; i++) {
			huffmanCode[i] = 400 + i - 144; // 400==110010000
			huffmanCodeLength[i] = 9;
		}
		for (i = 256; i <= 279; i++) {
			huffmanCode[i] = i - 256; // 0==0
			huffmanCodeLength[i] = 7;
		}
		for (i = 280; i < 286; i++) {
			huffmanCode[i] = 192 + i - 280; // 192==11000000
			huffmanCodeLength[i] = 8;
		}
		// reverse all:
		ZipHelper.revHuffTree(huffmanCode, huffmanCodeLength);

		// distHuffCode for non fixed DISTANCE tree
		for (int j = 0; j < distHuffCode.length; j++) {
			distHuffCode[j] = j;
			distHuffCodeLength[j] = 5;
		}
		// reverse all:
		ZipHelper.revHuffTree(distHuffCode, distHuffCodeLength);
	}

	/**
	 * This function generates the huffmann codes according to a given set of
	 * bitlegth.
	 * 
	 * @param huffmanCode
	 *            will be the resulting code pattern
	 * @param huffmanCodeLength
	 *            has to be the bitlegth for each code
	 */
	static final void genHuffTree(int[] huffmanCode, byte[] huffmanCodeLength) {
		int maxbits = 0;

		// generate bitlen_count
		for (int i = 0; i < huffmanCodeLength.length; i++) {
			int length = huffmanCodeLength[i];
			maxbits = maxbits > length ? maxbits : length;
		}
		maxbits++;

		short[] bitlen_count = new short[maxbits];
		for (int i = 0; i < huffmanCodeLength.length; i++) {
			bitlen_count[huffmanCodeLength[i]]++;
		}

		int code = 0;
		int[] next_code = new int[maxbits];
		bitlen_count[0] = 0;

		// find the Codes for each smallest Code within all of the same
		// bitlength
		for (int bits = 1; bits < maxbits; bits++) {
			// code=(code + bitlen_count[bits-1])*2;
			code = (code + bitlen_count[bits - 1]) << 1;
			next_code[bits] = code;
		}
		// generate all codes by adding 1 to the predecessor
		for (int i = 0; i < huffmanCode.length; i++) {
			byte length = huffmanCodeLength[i];
			if (length != 0) {
				huffmanCode[i] = next_code[length];
				next_code[length]++;
			}
		}

	}

	/**
	 * Compute the tree length according to the frequency of each code
	 * 
	 * @param count
	 * @param huffmanCodeLength
	 * @param max_len
	 */
	static final void genTreeLength(int[] count, byte[] huffmanCodeLength, int max_len) {
		int[] knotCount = new int[count.length];
		int[] knotPointer = new int[count.length];

		// initialise the knots
		for (short i = 0; i < count.length; i++) {
			if (count[i] != 0) {
				knotCount[i] = count[i];
			} else {
				knotCount[i] = Integer.MAX_VALUE;
			}
			knotPointer[i] = i;
		}

		// look for the smalest two knots
		int s1 = 0, s2 = 0;
		while (true) {

			// find Min1 and Min2
			if (knotCount[0] < knotCount[1]) {
				s1 = 0;
				s2 = 1;
			} else {
				s1 = 1;
				s2 = 0;
			}
			for (int i = 2; i < count.length; i++) {
				if (knotCount[i] < knotCount[s1]) {
					s2 = s1;
					s1 = i;
				} else if (knotCount[i] < knotCount[s2]) {
					s2 = i;
				}
			}

			// if we got all Minima -> exit
			if (knotCount[s2] == Integer.MAX_VALUE) {
				break;
			}

			// merge the knots
			knotCount[s1] += knotCount[s2];
			int tmp = knotPointer[s2];
			knotCount[s2] = Integer.MAX_VALUE;

			// set all knot pointer of Min2 -> Min1, add one to CodeLength, and
			// remove old knots from search
			for (int i = 0; i < count.length; i++) {
				if (knotPointer[i] == tmp) {
					knotPointer[i] = knotPointer[s1];
					huffmanCodeLength[i]++;
				} else if (knotPointer[i] == knotPointer[s1]) {
					huffmanCodeLength[i]++;
				}
			}

		}

		// check for overflow
		int overflowCount = 0;
		for (int i = 0; i < huffmanCodeLength.length; i++) {
			if (huffmanCodeLength[i] > max_len) {
				overflowCount++;
			}
		}
		// fix the overflow
		if (overflowCount != 0) {
			// #debug
			System.out.println(" fixing " + overflowCount + " overflows  because of max=" + max_len);

			// list the overflows
			short overflows[] = new short[overflowCount];
			overflowCount = 0;
			for (short i = 0; i < huffmanCodeLength.length; i++) {
				if (huffmanCodeLength[i] > max_len) {
					overflows[overflowCount++] = i;
				}
			}
			// find the index of the smalest node
			int minNode = 0;
			for (int i = 0; i < huffmanCodeLength.length; i++) {
				if (huffmanCodeLength[i] != 0 && huffmanCodeLength[minNode] > huffmanCodeLength[i]) {
					minNode = i;
				}
			}

			// ok lets go and fix it....
			int exendableNode;
			int overflow1, overflow2;
			while (overflowCount != 0) {
				exendableNode = minNode;
				// find the largest expandable length
				for (int i = 0; i < huffmanCodeLength.length; i++) {
					if (huffmanCodeLength[i] < max_len && huffmanCodeLength[exendableNode] < huffmanCodeLength[i]) {
						exendableNode = i;
					}
				}

				// find the deepest two overflows
				overflow1 = 0;
				overflow2 = 0;
				for (int i = 0; i < overflows.length; i++) {
					if (huffmanCodeLength[overflows[i]] > huffmanCodeLength[overflow1]) {
						overflow1 = overflows[i];

					} else if (huffmanCodeLength[overflows[i]] == huffmanCodeLength[overflow1]) {
						overflow2 = overflows[i];
					}
				}

				// insert one of them at the best exendableNode
				huffmanCodeLength[exendableNode]++;
				huffmanCodeLength[overflow1] = huffmanCodeLength[exendableNode];

				// lift the other one
				huffmanCodeLength[overflow2]--;

				// refresh the overflow count
				overflowCount--;
				if (huffmanCodeLength[overflow2] == max_len) {
					overflowCount--;
				}
			}
		}

	}

	/**
	 * In order to compute the CRC checksum fast it is crucial to have a
	 * precomputed table.
	 * 
	 * @param table
	 *            store the table here
	 */
	private static final void initCrc32Table(int[] table) {
		int c;

		int n, k;
		for (n = 0; n < 256; n++) {
			c = n;
			for (k = 0; k < 8; k++) {
				if ((c & 1) == 1) {
					c = 0xedb88320 ^ (c >>> 1);
				} else {
					c >>>= 1;
				}
			}
			table[n] = c;
		}
	}

	final static void revHuffTree(int[] huffmanCode, byte[] huffmanCodeLength) {
		// reverse all:
		int tmp;
		int reversed;
		for (int i = 0; i < huffmanCode.length; i++) {
			tmp = huffmanCode[i];
			reversed = 0;
			for (int j = 0; j < huffmanCodeLength[i]; j++) {
				reversed |= ((tmp >>> j) & 1);
				reversed <<= 1;
			}
			huffmanCode[i] = reversed >>> 1;
		}
	}

	/**
	 * This function skips the Gzip Header of a given stream.
	 * 
	 * @param in
	 *            the stream
	 * @throws IOException
	 *             ocurrs if the stream is not readable
	 */
	static final void skipheader(InputStream in) throws IOException {
		// check magic number and compression algorithm
		if (in.read() != 31 || in.read() != 139 || in.read() != 8) {
			// wrong gzip header
			throw new IOException("0");
		}

		int flag = in.read();
		in.skip(6);

		// skip FEXTRA
		if ((flag & 4) == 4) {
			in.skip(in.read() | in.read() << 8);
		}
		// skip FNAME
		if ((flag & 8) == 8) {
			while (in.read() != 0) {
				//
			}
		}
		// skip FCOMMENT
		if ((flag & 16) == 16) {
			while (in.read() != 0) {
				//
			}
		}
		// skip FHCRC
		if ((flag & 2) == 2) {
			in.skip(2);
		}

	}

	private ZipHelper() {}

}
